package day_2022_7_to_8.day48;

/**
 * @author haomin
 * @date 2022/08/21 09:54
 **/
public class Day36_2_Num74_SearchMatrix {
    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int m = matrix.length, n = matrix[0].length, i;
            for(i = 0; i < m; ++i){
                if(matrix[i][0] > target)
                    break;
            }
            if(--i < 0) return false;
            for(int j = 0; j < n; ++j){
                if(matrix[i][j] == target) return true;
            }
            return false;
        }
    }
    class Solution2 {
        public boolean searchMatrix(int[][] matrix, int target) {
            if(matrix.length == 0 || matrix[0].length == 0) return false;
            int m = matrix.length, n = matrix[0].length;
            int left = 0, right = m * n -1, mid;
            while(left <= right) {
                mid = left + ((right - left)>>1);
                if(matrix[mid/n][mid%n] > target) right = mid - 1;
                else if(matrix[mid/n][mid%n] < target) left = mid + 1;
                else return true;
            }
            return false;
        }
    }
}